package com.leetcode.demo20;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {

    /*public boolean isValid(String s) {
        Stack<Character>  brackets  = new Stack<Character>();
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            switch(c){
                case '(':
                case '[':
                case '{':
                    brackets.push(c);
                    break;
                case ')':
                    if(!brackets.empty()){
                        if(brackets.peek()== '('){
                            brackets.pop();
                        }else{
                            return false;
                        }
                    }else{
                        return false;
                    }
                    break;
                case ']':
                    if(!brackets.empty()){
                        if(brackets.peek()=='['){
                            brackets.pop();
                        }else{
                            return false;
                        }
                    }else{
                        return false;
                    }
                    break;
                case '}':
                    if(!brackets.empty()){
                        if(brackets.peek()=='{'){
                            brackets.pop();
                        }else{
                            return false;
                        }
                    }else{
                        return false;
                    }

            }
        }

        return brackets.empty();
    }*/

    /*public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int left, int right, int n){
        if (cur.length() == n * 2) {
            ans.add(cur);
            return;
        }
        //左括号不要超过 n
        if (left < n)
            backtrack(ans, cur+"(", left+1, right, n);
        //右括号不要超过左括号
        if (right < left)
            backtrack(ans, cur+")", left, right+1, n);
    }*/


/*    //这个方法是真的牛逼
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int a = 0; a < n; a++)
                for (String left: generateParenthesis(a))
                    for (String right: generateParenthesis(n-1-a))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }*/





}
